package 贪心;


import java.util.Arrays;

public class 贪心6_跳跃游戏II {

    public int jump_violence_dp(int[] nums){
        int[] res=new int[nums.length];//记录到达j处所需的最小步数
        //1.局部最优，很像动态规划,我们可以把res[i]看成是到达i位置处所需的最小位置，我们可以判断前面的哪些是+其原本的nums[x]的值之后可以到达该i处的
        //然后从这些中选取最小的步数res[x]来+1=res[i]
        for (int i = 1; i < nums.length; i++) {
            //1.遍历nums
            int Min= Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                //2.遍历i前面的
                if(nums[j]+j>=i){
                    //可以到达i
                    Min=Math.min(Min,res[j]);
                }
            }
            //因为第一次不会进去内部的for，所以Min不会被赋值，还是INT.MAX_VALUE，此时+1就会越界了。所以不要从i==0开始，因为i==0他前面没有别的res[x]。
            res[i]=Min+1;
        }
        System.out.println("nums:"+Arrays.toString(nums));
        System.out.println("res:"+Arrays.toString(res));

        return res[nums.length-1];
    }


    public int jump(int[] nums) {
        int[] res=new int[nums.length];
        //1.也是计算cover范围。
        int cover=0;
        for (int i = 0; i <= cover; i++) {
            if(cover>=nums.length-1)break;
            cover=Math.max(i+nums[i],cover);
            res[i]++;
        }
        System.out.println("nums:"+Arrays.toString(nums));
        System.out.println("res:"+Arrays.toString(res));

        if(cover<nums.length-1)return -1;//没说到达不了返回什么，该题默认能到达
        int Min= Integer.MIN_VALUE;
        for (int i = 0; i < res.length; i++) {
            Min=Math.max(Min,res[i]);
        }
        return Min;
    }

    public static void main(String[] args) {

        System.out.println(new 贪心6_跳跃游戏II().jump_violence_dp(new int[]{2,3,0,1,4}));
    }
}
